Computing mixed volume and all mixed cells in quermassintegral time

摘要

The mixed volume counts the roots of generic sparse polynomial systems. Mixedcells are used to provide starting systems for homotopy algorithms that canfind all those roots, and track no unnecessary path. Up to now, algorithms forthat task were of enumerative type, with no general non- exponential complexitybound. A geometric algorithm is introduced in this paper. Its complexity isbounded in the average and probability-one settings in terms of some geometricinvariants: quermassintegrals associated to the tuple of convex hulls of thesupport of each polynomial. Besides the complexity bounds, numerical resultsare reported. Those are consistent with an output- sensitive running time foreach benchmark family where data is available. For some of those families, anasymptotic running time gain over the best code available at this time wasnoticed.